/*
 * @lc app=leetcode.cn id=437 lang=javascript
 *
 * [437] 路径总和 III
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */

/**
 *  双递归
 */

// 获取以当前节点为开始的符合条件的个数
var dfs = function(root, targetSum){
  if(!root) return 0;
  let flag = root.val == targetSum ? 1 : 0;

  let left = dfs(root.left, targetSum - root.val);
  let right = dfs(root.right, targetSum - root.val);
  return flag + left + right;
}

// 便利所有节点，作为符合条件的第一个节点
var getCon = function(root, targetSum){
  if(!root) return 0;
  
  // 以当前节点开始的符合条件的个数
  let page = dfs(root, targetSum)
  // 以当前节点左节点开始的符合条件的个数
  let left = getCon(root.left, targetSum);
  let right = getCon(root.right, targetSum);
  return page + left + right;
}
var pathSum = function(root, targetSum) {
  if(!root) return 0;
  return getCon(root, targetSum)
};
// @lc code=end

